package com.explorati.LeetCode75.sortcolors;

/**
 * 75. Sort Colors 三路快排实现
 * 
 * @author explorati
 *
 */
public class Solution1 {
	public static void sortColors(int[] nums) {
		// lt指向最后一个比1小的元素，gt指向最后一个等于1的元素
		int lt = -1, gt = nums.length;
		int j = 0;
		// 终止条件，j==gt
		while (j < gt) {
			// 如果j位置元素小于1，则和lt+1位置元素互换，lt++,此时j向后移动
			if (nums[j] < 1) {
				swap(nums, ++lt, j);
				j++;
			}
			// 如果j位置元素大于1，则和gt-1的位置元素互换，且gt--，此时j不移动，因为gt-1位置元素不确定大小
			else if (nums[j] > 1) {
				assert nums[j] == 2;
				swap(nums, --gt, j);
			}
			// 若j位置元素等于1，则直接j++就可以
			else {
				assert nums[j] == 1;
				j++;
			}
		}

		// 错误的三路排序，思路误差：gt从前开始，这样当前位置小于一个数的时候，就出错了，由于将小的元素位置移到了大于的位置
		// for (int i = 0; i < nums.length; i++) {
		// // 如果i位置元素小于1，则和等于v第一个元素交换位置，lt++，gt++
		// if (nums[i] < 1) {
		// swap(nums, ++lt, i);
		// gt++;
		// }
		// // 如果i位置元素等于1，则将此位置元素和gt位置互换，gt++
		// if (nums[i] == 1) {
		// if (i != gt) {
		// swap(nums, gt++, i);
		// }
		// }
		// // 如果i位置元素大于1，直接gt++就可以
		// }
	}

	public static void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	public static void main(String[] args) {
		int[] arr = { 2, 0, 1, 3, 1, 0 };
		sortColors(arr);
		for (int i : arr) {
			System.out.print(i + "  ");
		}
	}
}
